package com.example.tourism.utils;

import java.util.ArrayList;
import java.util.List;

public class TSP {
    private int[][] distanceMatrix;
    private boolean[] visited;
    private int numCities;
    private List<Integer> tour ;
    private int totalCost;

    public TSP(int[][] distances) {  //初始化
        this.distanceMatrix = distances;
        this.numCities = distances.length;
        this.visited = new boolean[numCities];
        this.tour = new ArrayList<>();
        this.totalCost = 0;
    }

    private void solve(int startingCity) {
        tour.clear();
        visited[startingCity] = true;
        tour.add(startingCity);
        totalCost = 0;
        solveTSP(startingCity, 1);
    }
    private void solveTSP(int currentCity, int depth) {
        if (depth == numCities) {
            // 已经访问了所有城市，回到起点城市
            int lastCity = tour.get(tour.size() - 1);
            totalCost += distanceMatrix[lastCity][tour.get(0)];
            tour.add(tour.get(0));
            return;
        }
        int nearestCity = findNearestCity(currentCity);
        visited[nearestCity] = true;
        tour.add(nearestCity);
        totalCost += distanceMatrix[currentCity][nearestCity];
        solveTSP(nearestCity, depth + 1);
    }
    private int findNearestCity(int city) {
        int nearestCity = -1;
        int shortestDistance = Integer.MAX_VALUE;

        for (int i = 0; i < numCities; i++) {
            if (!visited[i] && distanceMatrix[city][i] < shortestDistance) {
                nearestCity = i;
                shortestDistance = distanceMatrix[city][i];
            }
        }

        return nearestCity;
    }
    public int getLength() { //获取总距离
        return totalCost;
    }
    public List<Integer> getPath(){ //获取总路线
        return tour;
    }
    public void run(int startingCity){  //运行一遍，计算路径
        solve(startingCity);
    }

}
